package LC;

import java.util.ArrayList;
import java.util.List;

/**
 * https://leetcode.com/problems/combinations/description/
 * Given two integers n and k, return all possible combinations of k numbers out of 1 ... n.
 * For example,
 * If n = 4 and k = 2, a solution is:
 * [
 * [2,4],
 * [3,4],
 * [2,3],
 * [1,2],
 * [1,3],
 * [1,4],
 * ]
 */
public class LC_077_Combinations_DFS_BackTracking {
    public static void main(String[] args) {
        System.out.println(Solution.combine(5, 3).toString());
    }

    static class Solution {
        static List<List<Integer>> combine(int n, int k) {
            List<List<Integer>> result = new ArrayList<>();
            if (n <= 0 || n < k)
                return result;
            ArrayList<Integer> item = new ArrayList<>();
            dfs(n, k, 1, item, result);
            return result;
        }

        private static void dfs(int n, int k, int start, ArrayList<Integer> item, List<List<Integer>> res) {
            if (item.size() == k) {
                res.add(new ArrayList<>(item));
                return;
            }
            for (int i = start; i <= n; i++) {
                item.add(i);
                dfs(n, k, i + 1, item, res);
                item.remove(item.size() - 1);
            }
        }
    }
}
